#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

class Solution2 {
public:
    vector<vector<string>> ans;
    vector<string> st;
    // 递归回溯
    void trackback(string s, vector<string> st){
        if (s.size() == 0){
            ans.push_back(st);
            return;
        }
        for (int i = 0; i < s.size(); i++){
            string bg = s.substr(0,i+1);
            if (isPalindrome(bg)){
                st.push_back(bg);
                trackback(s.substr(i+1),st);
                st.pop_back();
            }
        }
    }
    // 判断是否为回文串
    bool isPalindrome(string s){
        if (s.size() == 0) return true;
        int start = 0, end = s.size() - 1;
        while (start <= end) {
            if (s[start] != s[end])
                return false;
            start ++;
            end --;
        }
        return true;
    }
    // 主要函数
    vector<vector<string>> partition(string s) {
        trackback(s,st);
        return ans;
    }
};

class Solution {
    bool isPalindrome(string s) {
        if (s.size() == 0) return false;
        int l = 0, r = s.size()-1;
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
    // partition idx, end idx
    void dfs(string &s, vector<vector<string>> &answer, vector<string> &path, int pidx, int eidx) {
        if (s.size() == 0) return;
        string left = s.substr(0, pidx-0);
        string right = s.substr(pidx, eidx-pidx+1);

        if (!isPalindrome(left)) {
            return;
        }

        path.push_back(left);
        if (right.size() != 0) {
            if (isPalindrome(right)) {
                path.push_back(right);
                vector<string> a(path);
                answer.push_back(a);
                path.pop_back();
            }
            for (size_t i = 1; i < right.size(); i++)
                dfs(right, answer, path, i, right.size()-1);
        } else {
                vector<string> a(path);
                answer.push_back(a);
        }
        path.pop_back();
    }
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> answer;
        vector<string> path;
        for (size_t i = 1; i <= s.size(); i++)
            dfs(s, answer, path, i, s.size()-1);
        return answer;
    }
};

int main(void)
{

    cout << "#131. 分割回文串" << endl;
    string s = "1122aa";
    vector<vector<string>> ans = Solution().partition(s);
    int cnt = 0;
    for (auto e: ans) {
        cnt += 1;
        cout << cnt << ": ";
        for (auto it: e)
            cout << it << ", ";
        cout << endl;
    }

    ans = Solution2().partition(s);
    cout << "\nmethod 2:" << endl;

    cnt = 0;
    for (auto e: ans) {
        cnt += 1;
        cout << cnt << ": ";
        for (auto it: e)
            cout << it << ", ";
        cout << endl;
    }
    return 0;
}